package com.fps.webshop.question.question0100_0199;

import java.util.LinkedList;
import java.util.Queue;

import com.fps.webshop.question.common.TreeNode;

/**
 * 104. 二叉树的最大深度
 * 
 * 给定一个二叉树，找出其最大深度。
 * 
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 * 
 * 说明: 叶子节点是指没有子节点的节点。
 * 
 * 示例：
 * 给定二叉树 [3,9,20,null,null,15,7]，
 * 
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回它的最大深度 3 。
 */
public class Question104 {
	
	/**
	 * 第一次提交，二叉树递归调用
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		0 ms	38.4 MB	Java	2021/08/23 10:10
	 * 
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：38.4 MB, 在所有 Java 提交中击败了43.43%的用户
	 */
	public static int maxDepth1(TreeNode root) {
		return getMaxDeeth(root,0);
    }
	
	public static int getMaxDeeth(TreeNode root,int maxDeep) {
		if(root==null) {
			return maxDeep;
		}else {
			return Math.max(getMaxDeeth(root.left,maxDeep+1), getMaxDeeth(root.right,maxDeep+1));
		}
    }
	
	
	public static void main(String[] args) {
		TreeNode root = new TreeNode(41);
		TreeNode leftNode1 = new TreeNode(-57);
		TreeNode rightNode1 = new TreeNode(-57);
		root.left = leftNode1;
		root.right = rightNode1;
		
		TreeNode rightNode2 = new TreeNode(67);
		leftNode1.right = rightNode2;
		
		TreeNode leftNode3 = new TreeNode(67);
		rightNode1.left = leftNode3;
		
		System.out.print(maxDepth1(root));
		
	}
}
